/**
 * \* Created with IntelliJ IDEA.
 * \* User: 冯若航
 * \* Date: 2021/4/30
 * \* Time: 12:12
 * \* To change this template use File | Settings | File Templates.
 * \* Description:
 * \
 */
public class 打印从1到最大的n位数 {
//    public int[] printNumbers(int n) {
//        int end=(int)Math.pow(10,n)-1;
//        int res[]=new int[end];
//        for(int i=0;i<end;i++){
//            res[i]=i+1;
//        }
//        return res;
//    }

    /**
     * 解决大数打印
     * @param n
     * @return
     */

        int[] res;
        int nine = 0, count = 0, start, n;
        char[] num, loop = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};
        public int[] printNumbers(int n) {
            this.n = n;
            // 定义长度为 n 的字符列表
            res = new int[(int)Math.pow(10, n) - 1];
            num = new char[n];
            start = n - 1;
            dfs(0);
            return res;
        }
        void dfs(int x) {
            if(x == n) {
                String s = String.valueOf(num).substring(start);
                if(!s.equals("0")) {
                    res[count++] = Integer.parseInt(s);
                }
                if(n - start == nine) {
                    start--;
                }
                return;
            }
            for(char i : loop) {
                if(i == '9') {
                    nine++;
                }
                num[x] = i;
                dfs(x + 1);
            }
            nine--;
        }


}